#define _CRT_SECURE_NO_WARNINGS 1

#include<iostream>
#include<string>

using namespace std;

struct TreeNode {
    int val;
    TreeNode* left;
    TreeNode* right;
    TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};

void _serialize(TreeNode* root, string& res)
{
    if (root == nullptr)
    {
        return;
    }

    res += to_string(root->val);
    res.push_back(' ');
    _serialize(root->left, res);
    _serialize(root->right, res);
}

string serialize(TreeNode* root) {
    string res;
    _serialize(root, res);
    return res;
}

// Decodes your encoded data to tree.
TreeNode* deserialize(string data) {
    if (data.size() == 0)
        return nullptr;
    TreeNode* root = nullptr;
    int pos = 0;
    while (pos < data.size())
    {
        int newn = data.find(" ", pos);
        string s = data.substr(pos, newn - pos);
        int num = stoi(s);
        newn++;
        pos = newn;
        TreeNode* newnode = new TreeNode(num);
        if (root == nullptr)
        {
            root = newnode;
            continue;
        }
        TreeNode* cur = root;
        TreeNode* prev = nullptr;
        while (cur)
        {
            prev = cur;
            if (num < cur->val)
                cur = cur->left;
            else if (num > cur->val)
                cur = cur->right;
        }
        if (num < prev->val)
            prev->left = newnode;
        else
            prev->right = newnode;
    }
    return root;
}

int main()
{
    TreeNode* root = new TreeNode(2);
    TreeNode* left = new TreeNode(1);
    TreeNode* right = new TreeNode(3);
    root->left = left;
    root->right = right;
    string tree = serialize(root);
    TreeNode* Tree = deserialize(tree);
    return 0;
}